package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.ShowUtil;

import java.util.ArrayList;
import java.util.List;

public class code93_复原IP地址 {

    public static void main(String[] args) {
        List<String> list = new code93_复原IP地址().restoreIpAddresses("010010");
        ShowUtil.showList(list, true);
    }

    public List<String> restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) {
            return new ArrayList<>();
        }

        int fullNum = (s.length() - 4) / 3;
        int minNum = s.length() - fullNum * 3;
        List<String> list = new ArrayList<>();
        ans(0, 0, new String[4], list, s.toCharArray());
        return list;
    }

    /*
    (3-base)*speed >=other
     */
    public void ans(int start, int speed, String[] item, List<String> list, char[] chars) {
        if (speed >= 4) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int a = 0; a < 4; a++) {
                stringBuilder.append(a == 0 ? "" : ".").append(item[a]);
            }
            list.add(stringBuilder.toString());
            return;
        }
        if(start>=chars.length){
            return ;
        }
        char[] num = new char[3];
        int index = 0;

        if (chars[start] == '0') {
            if (canCreate(start + 1, chars.length, speed + 1)) {
                item[speed] = "0";
                ans(start + 1, speed + 1, item, list, chars);
            }
        } else {
            for (int a = 0; a < 3 && start + a < chars.length; a++) {
                num[index] = chars[start+a];
                index++;
                if (canCreate(start + a + 1, chars.length, speed + 1)) {
                    int n = getNum(num, index);
                    if (n >= 0 && n <= 255) {
                        item[speed] = new String(num, 0, index);
                        ans(start + a + 1, speed + 1, item, list, chars);
                    }
                }
            }
        }
    }

    public boolean canCreate(int nowNumber, int allNumber, int speed) {
        if (allNumber - nowNumber > (4 - speed) * 3) {
            return false;
        } else {
            return true;
        }
    }

    private int getNum(char[] num, int index) {
        int base = num[0] - '0';
        for (int a = 1; a < index; a++) {
            base = base * 10 + num[a] - '0';
        }
        return base;
    }

    public List<String> restoreAllIpAddresses(String s) {
        if (s.length() < 4) {
            return new ArrayList<>();
        }
        List<String> list = new ArrayList<>();
        ansAllIp(s.toCharArray(), 0, 0, list, new String[4]);
        return list;
    }


    public void ansAllIp(char[] chars, int start, int speed, List<String> list, String[] item) {
        if (speed >= 4) {
            addAll(chars, list);
            return;
        }
        char[] num = new char[3];
        for (int a = start; a < chars.length; a++) {
            int index = 0;
            for (int sp = 0; a + sp < chars.length - 3 && sp < 3; sp++) {
                num[index] = chars[a + sp];
                index++;
                int n = getNum(num, index);
                if (n >= 0 && n <= 255) {
                    item[speed] = new String(num, 0, index);
                    ansAllIp(chars, a + sp + 1, speed + 1, list, item);
                }
            }
        }
    }

    private void addAll(char[] chars, List<String> list) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int a = 0; a < 4; a++) {
            stringBuilder.append(a == 0 ? "" : ",").append(chars[a]);
        }
        list.add(stringBuilder.toString());
    }

}
